package com.yuan.algorithms.面试题;


/**
 * 给定整数 n 和 k，返回  [1, n] 中字典序第 k 小的数字。
 * 1 <= k <= n <= 1000000000
 *
 * 示例 1:
 * 输入: n = 13, k = 2
 * 输出: 10
 * 解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
 *
 * 示例 2:
 * 输入: n = 1, k = 1
 * 输出: 1
 *
 * 题目链接：https://leetcode-cn.com/problems/k-th-smallest-in-lexicographical-order
 *
 * 解题思路：
 * n=99时的字典序列：
 * 1,10,11,12,13,14,15,16,17,18,19,
 * 2,20,21,22,23,24,25,26,27,28,29,
 * 3,30,31,32,33,34,35,36,37,38,39,
 * 4,40,41,42,43,44,45,46,47,48,49,
 * 5,50,51,52,53,54,55,56,57,58,59,
 * 6,60,61,62,63,64,65,66,67,68,69,
 * 7,70,71,72,73,74,75,76,77,78,79,
 * 8,80,81,82,83,84,85,86,87,88,89,
 * 9,90,91,92,93,94,95,96,97,98,99
 * 可以利用数据的周期性重复特性来优化计算量
 *
 * @author YouYuan
 * @date 2022/3/23 14:47
 */
public class 字典序的第K小数字 {

    // 是否打印序列
    public static final boolean printSeq = false;
    public static final boolean test = false;

    public static void main(String[] args) {
        int n = 596516650;
        int k = 593124772;
        Solution solution = new Solution();
        long s = System.currentTimeMillis();
        solution.findKthNumber(n, k);
        long e = System.currentTimeMillis();
        System.out.printf("%n递归rs:%d use time:%d%n", rs, (e-s));

        s = System.currentTimeMillis();
        int answer = lawCalculate(n, k);
        e = System.currentTimeMillis();
        System.out.printf("循环answer:%d use time:%d%n", answer, (e-s));

        s = System.currentTimeMillis();
        int simpleAns = simpleCalculate(n, k);
        e = System.currentTimeMillis();
        System.out.printf("优化simpleAns:%d use time:%d%n", simpleAns, (e-s));

        if (test) {
            for (int i = 101; i < 1000000; i++) {
                n = i;
                k = i >> 1;
                solution.findKthNumber(n, k);
                int srs = simpleCalculate(n, k);
                if (srs != rs) {
                    throw new RuntimeException("答案不匹配！n=" + n + ", k=" + k);
                }
                if (i % 10000 == 0) {
                    System.out.println(i / 100000);
                }
            }
        }
    }

    /**
     * 结合字典序列规律，从接近k的位置开始计算
     *
     * 执行结果： 通过
     * 执行用时：
     * 572 ms , 在所有 Java 提交中击败了 12.52% 的用户
     * 内存消耗： 38.1 MB , 在所有 Java 提交中击败了 73.96% 的用户
     * 通过测试用例： 69 / 69
     * @param n
     * @param k
     * @return
     */
    private static int simpleCalculate(int n, int k) {
        int x = 0;
        int temp = n;
        int size = 1;
        while (temp / 10 > 0) {
            temp /= 10;//获得n的最高位
            x++;
        }
        if (temp - 1 > 0 && x > 0) {
            int step = temp;//可以跳到n的最高位-1位，例如5330可以尝试从5开始计算
            while (x > 0) {
                size = size * 10 + 1;//单层序列个数
                x--;
            }
            int c = k / size;//计算k在第几层
            int m = k % size;//计算k在第几位
            if (m == 0) {
                //如果k在该层的最后一位，可以直接计算出该位置的值
                temp = n;
                int result = c;
                while (temp / 10 > 0) {
                    temp /= 10;//获得n的最高位
                    result = result * 10 + 9;
                }
                return result;
            }
            if (step <= c) {
                //k的位置在最后一层，那么最多只能跳到倒数第二层
                c--;
            }
            if (c > 0 && step > c) {
                int i = c * size;//跳过元素个数
                return lawCalculate(n, k, i + 1, c + 1);
            }
        }
        return lawCalculate(n, k);
    }

    /**
     * 从第i个位置开始推导元素
     * @param n
     * @param k
     * @param i
     * @param s
     * @return
     */
    private static int lawCalculate(int n, int k, int i, int s) {
        long cur = i;
        long curN = s;
        int tempN = n;
        int nLen = 0;//n的进位长度
        while (tempN / 10 > 0) {
            tempN /= 10;
            nLen++;
        }
        while (cur < k) {
            curN = curN * 10;
            if (curN > n) {
                curN = curN / 10;
                if (curN % 10 == 0) {
                    if (curN + 9 < n) {
                        if (cur + 9 < k) {
                            cur += 9;
                        } else {
                            curN = curN + k - cur;
                            cur = k;
                            break;
                        }
                    } else {
                        long len = n - curN;
                        if (cur + len < k) {
                            cur += len;
                            curN += len;
                        } else {
                            curN = curN + k - cur;
                            cur = k;
                            break;
                        }
                    }
                    curN = curN / 10 + 1;
                } else {
                    curN++;
                }
                boolean mark = false;//进入优化标识
                while (curN % 10 == 0) {
                    /**
                     * 在此发生了进位，此处可以优化计算量
                     */
                    curN /= 10;
                    mark = true;
                }
                cur++;
                if (mark) {
                    //进位优化，尝试跳过当前数值到下次进位的计算
                    long temp = curN;
                    for (int j = (int) (temp % 10); j <= 9; j++) {
                        long next = curN + 1;
                        int tempLen = 0;
                        while (temp / 10 > 0) {
                            temp /= 10;
                            tempLen++;
                        }
                        int x = nLen - tempLen;
                        int seqLen = 1;
                        if (x > 0) {
                            long tempNext = next;
                            while (x > 0) {
                                tempNext *= 10;
                                seqLen = seqLen * 10 + 1;
                                x--;
                            }
                            if (tempNext <= n && cur + seqLen <= k) {
                                // 满足优化条件，跳过当前值后面的序列，直接进入下一层
                                cur += seqLen;
                                curN = next;
                                temp = curN;
                            } else {
                                break;
                            }
                        }
                    }
                    while (curN % 10 == 0) {
                        // 可能因为优化导致进位，进位后的数应该是个位不为0的
                        curN /= 10;
                    }
                }
            } else {
                cur++;
            }
        }
        return (int) curN;
    }

    /**
     * 使用循环推导第k位元素
     * 60 / 69 个通过测试用例，报超时
     * @param n
     * @param k
     * @return
     */
    private static int lawCalculate(int n, int k) {
        return lawCalculate(n, k, 1, 1);
    }

    public static long count = 0;
    public static long rs = 0;

    /**
     * 递归生成字典序数列，并保存第k位数
     * 整体执行速度并不慢，但是不满足leetcode运行时间要求，提交答案报超时，答案通过率43/69
     * 可以通过递归输出序列，查找序列的规律，通过规律来寻找更优化的解法，并且能够验证答案是否正确
     * 所有数字使用Long，避免因为int溢出导致计算错误
     * @param i
     * @param n
     * @param k
     */
    private static void dict(long i, long n, long k) {
        if (i > 0 && i <= n && count < k) {
            if (printSeq) {
                System.out.print(i + ",");
            }
            count++;
            if (k == count) {
                rs = i;
                return;
            }
            dict(i * 10, n, k);
            if (count >= k) {
                return;
            }
            for (long j = 1, sum = i + j; j <= 9 && sum <= n; j++, sum++) {
                if (printSeq) {
                    System.out.print(sum + ",");
                }
                count++;
                if (k == count) {
                    rs = sum;
                    return;
                }
                if (count > k) {
                    return;
                }
                dict(sum*10, n, k);
                if (count >= k) {
                    return;
                }
            }
        }
    }

    static class Solution {
        public long findKthNumber(long n, long k) {
            rs = 0;
            count = 0;
            dict(1, n, k);
            return rs;
        }

    }

}
